A directed acyclic graph (DAG) is a useful representation for verifying compliance to a constraint that may be a set of individual constraints. Example constraints are a time constraint, such as a schedule for completing a project with multiple dependencies, and a distance constraint, such as a requirement that certain interrelated components must be arranged to fit within an available space.
Another example for a timing constraint is static timing analysis of an electronic circuit, which may have the requirement that particular circuit paths have a cumulative delay along the path that is less than or greater than a given value, which may be explicitly or implicitly specified. For static timing analysis, the DAG may have nodes representing circuit elements and arcs representing connections between the circuit elements. Each arc or node may have an associated delay value representing the propagation delay through the arc or node. By adding the delay values for the arcs and/or nodes along the path, the total propagation delay along the path may be determined and compared with the path requirement.
A DAG has a set of source nodes and a set of sink nodes. Typically, a constraint for a DAG is a constraint between some of the source nodes and some of the sink nodes. Numerous paths may exist between a particular source and a particular sink. A graph search of the DAG may efficiently determine the worst case paths. Enumeration of all paths represented by the DAG may be avoided because the DAG satisfies the constraint if the worst case paths satisfy the constraint.
A relaxation of a constraint may specify that certain paths between a source and a sink may be disregarded in verifying compliance to the constraint, or may have a relaxed requirement. The relaxation overrides the constraint. Example relaxations are multi-cycle paths and false paths for a synchronous electronic circuit, or false or irrelevant paths in an asynchronous circuit.
An example multi-cycle path in a synchronous electronic circuit may have a source that is known, a priori, to change the transmitted value only in even clock cycles and a sink that is known, a priori, to ignore the received value in odd clock cycles. Thus, this particular path may provide correct circuit operation when the cumulative delay along the path is as much as two clock periods. A constraint that paths have a total delay of less than one clock period may be relaxed for the multi-cycle path.
An example false path in a synchronous electronic circuit may be an apparent path that is impossible to exercise. For example, a multiplexer control signal may control two separate multiplexers, and a path from a source to a sink may pass through a different respective input of each multiplexer. The propagation of signal values along the path is then interrupted, regardless of the value of the multiplexer control signal, by one of the multiplexers. Because a value change of the source cannot propagate along the path to a value change of the sink, the cumulative delay along the path may be unconstrained. A constraint that paths have a total delay of less than one clock period may be relaxed for the false path.
One approach to representing a relaxation of a constraint is to perform node replication and select arc replication and removal within the DAG to isolate the relaxation paths from the remaining constraint paths. However, the duplicated nodes in the DAG may complicate other graph operations, such as node searches.
The present invention may address one or more of the above issues.